from collections import deque
from bisect import (bisect_right as rbisect, 
                    bisect_left  as lbisect)

from khronos.utils.misc import INF, identity_fnc

class Deque(deque):
    """A deque class with extended functionality. This class supports indexed insertion and 
    deletion, and sorted insertion and deletion."""
    def __repr__(self):
        return "%s(%s)" % (self.__class__.__name__, list(self))
        
    def copy(self):
        return self.__class__(self)
        
    def insert_at(self, pos, item):
        """Insert 'item' at index 'pos'. Supports negative indices."""
        if pos < 0:
            pos += len(self)
            if pos < 0:
                raise IndexError("deque index out of range")
        self.rotate(-pos)
        self.appendleft(item)
        self.rotate(pos)
        
    def pop_at(self, pos):
        """Pop and return the item at index 'pos'. Supports negative indices."""
        item = self[pos]
        del self[pos]
        return item
        
    def insert_sorted(self, item, key=None, after=True, lo=0, hi=INF):
        """Insert 'item' in order using binary search for finding the point of insertion.
        point. A 'key' argument may be passed to specify how 'item' compares to other elements 
        in the deque. If after is True (default) the element is inserted after equal elements, 
        otherwise it is inserted before (to the left) equal elements."""
        bisect = self.bisect_right if after else self.bisect_left
        position = bisect(item, key, lo, hi)
        self.insert_at(position, item)
        return position
        
    def remove_sorted(self, item, key=None, exact=False, lo=0, hi=INF):
        """Remove 'item' in order taking advantage of list bisection. If 'exact' is True, the 
        removed object MUST BE the same object (same id) as 'item', otherwise the first object 
        (leftmost) which compares to equal (using 'key') is removed."""
        pos = self.bisect_right(item, key, lo, hi) - 1
        # Item not found in the deque, raise exception.
        if pos == -1:
            raise ValueError("%s not found in %s" % (item, self))
            
        if key is None:
            key = identity_fnc
        item_key = key(item)
        # Perform different actions based on the 'exact' flag.
        if exact:
            while pos >= 0:
                other_item = self[pos]
                if item is other_item:
                    break
                if key(other_item) < item_key:
                    raise ValueError("%s not found in %s" % (item, self))
                pos -= 1
            if pos == -1:
                raise ValueError("%s not found in %s" % (item, self))
        else:
            other_item = self[pos]
            other_key = key(other_item)
            if other_key < item_key:
                raise ValueError("%s not found in %s" % (item, self))
            assert other_key == item_key
        # Finally remove the correct item from the deque.
        del self[pos]
        return pos
        
    def bisect_left(self, item, key=None, lo=0, hi=INF):
        lo = max(lo, 0)
        hi = min(hi, len(self))
        if key is None:
            # If no key function was provided, use bisect.bisect_left().
            return lbisect(self, item, lo, hi)
        else:
            # The bisection loop using a custom key function.
            while lo < hi:
                pos = lo + (hi - lo) / 2
                if key(item) > key(self[pos]):
                    lo = pos + 1
                else:
                    hi = pos
            return lo
            
    def bisect_right(self, item, key=None, lo=0, hi=INF):
        lo = max(lo, 0)
        hi = min(hi, len(self))
        if key is None:
            # If no key function was provided, use bisect.bisect_right().
            return rbisect(self, item, lo, hi)
        else:
            # The bisection loop using a custom key function.
            while lo < hi:
                pos = lo + (hi - lo) / 2
                if key(item) >= key(self[pos]):
                    lo = pos + 1
                else:
                    hi = pos
            return lo
            
    def sort(self, cmp=None, key=None, reverse=False):
        """In-place deque sorting. Supports the same arguments as the built-in sorted()."""
        new_order = sorted(self, cmp=cmp, key=key, reverse=reverse)
        self.clear()
        self.extend(new_order)
        
    insort  = insert_sorted
    outsort = remove_sorted
    bisect  = bisect_right
    
#    def priority_push(self, item, key=identity_fnc):
#        self.append(item)
#        self.__up_heap(key)
#        
#    def priority_pop(self, item, key=identity_fnc):
#        item = self.popleft()
#        self.rotate(1)
#        self.__down_heap(key)
#        return item
#        
#    def __up_heap(self, key):
#        child = len(self) - 1
#        parent = int((child - 1) / 2)
#        while key(parent) < key(child) and parent >= 0:
#            self[parent], self[child] = self[child], self[parent]
#            child = parent
#            parent = int((child - 1) / 2)
#            
#    def __down_heap(self, key):
#        parent = 0
#        left = parent * 2 + 1
#        right = left + 1
#        left_key = key(self[left])
#        right_key = key(self[right])
#        highest_child = left
#        highest_key = left_key
#        if left_key < right_key:
#            highest_child = right
#            highest_key = right_key
#        while key(parent) < highest_key:
#            self[parent], self[child] = self[child], self[parent]
#        # STILL INCOMPLETE !!!
            